Theory of Computation
Q2.
For a string w, we define w^R to be the reverse of w. For example, if w=01101 then w^R=10110. Which of the following languages is/are context-free?[MSQ]Q3.
Consider the following languages: \begin{aligned} L_1&= \{a^n wa^n|w \in \{a,b \}^* \} \\ L_2&= \{wxw^R | w,x \in \{a,b \}^*, |w|,|x| \gt 0 \} \end{aligned}Note that w^R is the reversal of the string w. Which of the following is/are TRUE?MSQQ4.
Consider the following languages: \begin{aligned} L_1&= \{ ww|w \in \{a,b \}^* \} \\ L_2&= \{a^nb^nc^m | m,n \geq 0 \} \\ L_3 &= \{a^mb^nc^n|m,n \geq 0 \} \end{aligned}Which of the following statements is/are FALSE?MSQQ5.
Consider the following languages. L_1=\{wxyx|w,x,y \in (0+1)^+\} L_2=\{xy|x,y \in (a+b)^*,|x|=|y|,x\neq y\} Which one of the following is TRUE?Q6.
Suppose that L_1 is a regular language and L_2 is a context-free language. Which one of the following languages is NOT necessarily context-free?Q7.
Let L_1 be a regular language and L_2 be a context-free language. Which of the following languages is/are context-free?[MSQ]Q8.
Let L_{1},L_{2} be any two context free languages and R be any regular language. Then which of the following is/are CORRECT ? I. L_{1}\cup L_{2} is context - free II. \bar{L_{1}} is context - free III. L_{1} - R is context - free IV. L_{1}\cap L_{2} is context - freeQ9.
Consider the language L=\{a^n|n\geq 0\}\cup \{a^nb^n|n\geq 0\} and the following statements. I. L is deterministic context-free. II. L is context-free but not deterministic context-free. III. L is not LL(k) for any k. Which of the above statements is/are TRUE?Q10.
Consider the following languages L_{1}=\{a^{p}|p is a prime number} L_{2}=\{a^{n}b^{m}c^{2m}|n\geq 0,m\geq 0\} L_{3}=\{a^{n}b^{n}c^{2n}|n\geq 0\} L_{4}=\{a^{n}b^{n}|n\geq 1\} Which of the following are CORRECT ? I.L_{1} is context-free but not regular. II. L_{2} is not context-free. III. L_{3} is not context-free but recursive. IV. L_{4} is deterministic context-free.